package dynamic_programming;
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/59gq9c/
//某公司每日销售额记于整数数组 sales，请返回所有 连续 一或多天销售额总和的最大值。
//要求实现时间复杂度为 O(n) 的算法。
public class LCR_161连续天数的最高销售额 {
    //动态规划
    class Solution {
        public int maxSales(int[] sales) {
            if(sales.length == 1) return sales[0];
            int res = sales[0];
            for(int i=1; i<sales.length; i++){
                sales[i] += Math.max(sales[i-1],0);
                res = Math.max(res,sales[i]);
            }
            return res;
        }
    }
    //暴力 超时
    class Solution2 {
        public int maxSales(int[] sales) {
            int max = Integer.MIN_VALUE;
            for(int i=0; i<sales.length; i++){
                int sum = 0;
                for(int j=i; j<sales.length; j++){
                    sum += sales[j];
                    if(sum > max)
                        max = sum;
                }
            }
            return max;
        }
    }
    //前缀和
    class Solution3 {
        public int maxSales(int[] sales) {
            int min = 0;
            int ans = Integer.MIN_VALUE;
            int sum = 0;
            for(int i=0; i<sales.length; i++){
                sum += sales[i];
                ans = Math.max(ans,sum-min);
                if(sum < min)
                    min = sum;
            }
            return ans;
        }
    }
    //线段树
    class Solution4 {
        public class Status {
            public int lSum, rSum, mSum, iSum;

            public Status(int lSum, int rSum, int mSum, int iSum) {
                this.lSum = lSum;
                this.rSum = rSum;
                this.mSum = mSum;
                this.iSum = iSum;
            }
        }

        public int maxSales(int[] sales) {
            return getInfo(sales, 0, sales.length - 1).mSum;
        }

        public Status getInfo(int[] a, int l, int r) {
            if (l == r) {
                return new Status(a[l], a[l], a[l], a[l]);
            }
            int m = (l + r) >> 1;
            Status lSub = getInfo(a, l, m);
            Status rSub = getInfo(a, m + 1, r);
            return pushUp(lSub, rSub);
        }

        public Status pushUp(Status l, Status r) {
            int iSum = l.iSum + r.iSum;
            int lSum = Math.max(l.lSum, l.iSum + r.lSum);
            int rSum = Math.max(r.rSum, r.iSum + l.rSum);
            int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
            return new Status(lSum, rSum, mSum, iSum);
        }
    }
}
